package practice;

import struct.ListNode;

/**
 * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
 * 示例 1:
 *
 * 输入: 1->1->2
 * 输出: 1->2
 * 示例 2:
 *
 * 输入: 1->1->2->3->3
 * 输出: 1->2->3
 */
public class _83_DeleteDuplicates {

    /**
     * 思路：
     * 遍历链表，保存上一个不同的元素preNode
     * 当当前元素与preNode不同时，将preNode的next指向该元素，继续遍历
     * 当它们相同时，继续遍历，直到找到不同的元素
     * 最后，清空后续相同的元素，防止链表末尾元素为重复元素
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode node = head.next,preNode = head;
        while (node != null){
            if(node.val == preNode.val){
                node = node.next;
            } else {
                preNode.next = node;
                preNode = node;
                node = node.next;
            }
        }
        //清空后续相同的元素
        preNode.next = null;
        return head;
    }
}
